#include<iostream>
#include<fstream>
#include<stack>
#include<string>

#include<queue>

#define INFINITY 9999
using namespace std;

class UpSet
{
private:
    /* data */
    int n;
    int *root;
    int *next;
    int *length;

public:
    UpSet(int size/* args */)
    {
        n = size;
        root = new int[size];
        next = new int[size];
        length = new int[size];
        for (int i = 0; i < n; i++)
        {
            root[i] = next[i] = i;
            length[i] = 1;
        }
    }
    ~UpSet();
    int Find(int v)
    {
        return root[v];
    }
    void Union(int v, int u)
    {
        if(root[u]==root[v])
        {
            return;
        }
        else if(length[root[v]]<length[root[v]])
        {
            int rt = root[v];
            length[root[u]] += length[rt];
            root[rt] = root[u];
            for (int j = next[rt]; j != rt;j = next[j])
            {
                root[j] = root[u];
            }
            int temp;
            temp = next[rt];
            next[rt] = next[root[u]];
            next[root[u]] = temp;
        }
        else
        {
            int rt = root[u];
            length[root[v]] += length[rt];
            root[rt] = root[v];
            for (int j = next[rt]; j != rt;j = next[j])
            {
                root[j] = root[v];
            }
            int temp;
            temp = next[rt];
            next[rt] = next[root[v]];
            next[root[v]] = temp;
        }
        
    }
};

class Dist
{
public:
    int length;
    int pre;
};

UpSet::~UpSet()
{
    delete[] root;
    delete[] next;
    delete[] length;
}

class MapMatrix
{
public:
    char * mVexs;
    int mVexNum;
    int mEdgNum;
    int **mMatrix;
    MapMatrix(int num);
    int GetPos(char Character);
    void Insert(string address);
    ~MapMatrix();
    void DFSsearch();
    void DFSRsearch(int i, int * visit);
    void BFSsearch();
    void BFSRsearch(int i, int * visit);
    void Prim();
    void Kruskal();
    Dist *Dijikstra(int s);
    Dist **Flyod();
   
    void Print(int **Matr)
    {
        for (int i = 0; i < mVexNum;i++)
        {
            for (int j = 0; j < mVexNum;j++)
            {
                if(Matr[i][j] != INFINITY)
            cout << Matr[i][j] << " ";
            else
                cout << "/"
                     << " ";
            }
            cout << endl;
        }
    }
    void Init(int **Matr)
    {
        for (int i = 0; i < mVexNum;i++)
        {
            for (int j = 0; j < mVexNum;j++)
            {
                Matr[i][j] = INFINITY;
            }
        }
    }
};

MapMatrix::MapMatrix(int num)
{
    mVexs = new char[num];
    mMatrix = new int*[num];
    mEdgNum = 0;
    
    for (int i = 0; i < num; i++)
    {
        mMatrix[i] = new int[num];
    }
    
    for(int i = 0;i<num;i++)
    {
        for(int j = 0;j<num;j++)
        {
            if(mMatrix[i][j]!=0)
            {
                mEdgNum++;
            }
        }
    }
    
    mVexNum = num;
    
}

MapMatrix::~MapMatrix()
{
    for(int i = 0;i<mVexNum;i++)
    {
        delete[] mMatrix[i];
    }
    delete[] mMatrix;
}

void MapMatrix::Insert(string address)
{
    fstream file;
    file.open(address);
    for (int i = 0; i < mVexNum;i++)
    {
        file >> mVexs[i];
    }
    for (int i = 0; i < mVexNum;i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            string a;
            file >> a;
            //cout << "a = " << a << " ";
            if (a != "/")
                mMatrix[i][j] = stoi(a);
            else
                mMatrix[i][j] = INFINITY;
            //cout << i << ":" << j << " " << mMatrix[i][j] << endl;
        }
    }
    
    for (int i = 0; i < mVexNum;i++)
    {
        cout<< mVexs[i]<<" ";
    }
    cout << endl;
    Print(mMatrix);
    file.close();
}

void MapMatrix::DFSsearch()
{
    int i;
    int visited[mVexNum];

    for (i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
    }
    cout << "进行DFS递归查找: ";
    for (i = 0; i < mVexNum;i++)
    {
        if(!visited[i])
        {
            DFSRsearch(i, visited);
            
        }
    }
    cout << endl;
    for (i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
        
    }
    //getchar();
    cout << "进行DFS非递归查找：";
    stack<int> stackForSearch;
    
    for (int k = 0; k < mVexNum; k++)
    {
        if(!visited[k])
        {
             stackForSearch.push(k);
            while(!stackForSearch.empty())
            {
                i = stackForSearch.top();
                if(!visited[i])
                {
                    cout << mVexs[i] << " ";
                    visited[i] = 1;
                }

                int j;
                for (j = 0; j < mVexNum; j++)
                {
                //cout<<"此时i的值为" <<i<<",j的值为"<<j<< endl;
                if(!visited[j]&&mMatrix[i][j]!=0)
                {
                  //  cout << "放入" << endl;
                    stackForSearch.push(j);
                    break;
                }
                //getchar();
                }
                if(j==mVexNum&&!stackForSearch.empty()) 
                {
                    stackForSearch.pop();
                }
            
           
            }
        }
    }
    cout << endl;
}

void MapMatrix::DFSRsearch(int i,int * visited)
{
    
    int w;
    visited[i] = 1;
    cout << mVexs[i] << " ";
    
    for (int j = 0; j < mVexNum; j++)
    {
        w = mMatrix[i][j];
        /*if(i==1&&j==2)
        {
            cout<<"此时i的值为" <<i<<",j的值为"<<j<< endl;
            cout << mVexs[j] << endl;
            cout << w << endl;
            cout << "!!!" << endl;
            for (int l = 0; l < 5; l++)
                cout <<"l = "<<l<<":"<< visited[l] << endl;
            cout << mMatrix[i][j] << endl;
        }*/

        if(!visited[j]&&mMatrix[i][j]!=0)
        {
            //cout << mVexs[i] << "与" << mVexs[j] << "之间有连接," << endl;
            DFSRsearch(j, visited);
        }
    }
}

void MapMatrix::BFSsearch() // 这个有带你问题
{
    int i;
    int visited[mVexNum];

    for (i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
    }
    cout << "进行BFS递归查找: ";
    for (i = 0; i < mVexNum;i++)
    {
        queue<int> queueForSearch;
        if(!visited[i])
        {
            
            queueForSearch.push(i);
            int w = i;
            while (!queueForSearch.empty())
            {
                //cout << "are you doing this?" << endl;
                w = queueForSearch.front();
                if(!visited[w])
                cout << mVexs[w] << " ";
                visited[w] = 1;
                queueForSearch.pop();
                int j;
                for (j = 0; j < mVexNum; j++)
                {
                    if(!visited[j]&&mMatrix[w][j]!=INFINITY)
                    {
                        queueForSearch.push(j);
                        
                    }
                }
                
            }
        }
    }
    cout << endl;
}

void MapMatrix::Prim() //GRAPH in PPT
{
    vector<int> U;

    int visited[mVexNum];
    for (int i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
    }
    int **mNewMatrix;
    mNewMatrix = new int*[mVexNum];
    //先生成新的矩阵
    for (int i = 0; i < mVexNum; i++)
    {
        mNewMatrix[i] = new int[mVexNum];
    }
    
    for (int i = 0; i < mVexNum;i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            mNewMatrix[i][j] = INFINITY;
        }
    }
    U.push_back(0);
    visited[0] = 1;
    while (U.size() < 6)
    {
        int SmallestNum = INFINITY;
        int LeftPos = INFINITY;
        int position = INFINITY;
        int i;
        for (int k = 0; k < U.size(); k++)
        {
            i = U[k];
            //cout << "i = " << i << endl;
            //getchar();
            for (int j = 0; j < mVexNum; j++)
            {
                if(mMatrix[i][j]<SmallestNum&&visited[j] == 0)
                {
                    SmallestNum = mMatrix[i][j];
                    position = j;
                    LeftPos = i;
                }
            }
            //cout << "SmallestNum = " << SmallestNum << endl;
            //cout << "X: " << LeftPos << ",Y: " << position << endl;
        }
        if(SmallestNum!=INFINITY)
        {
            U.push_back(position);
            mNewMatrix[LeftPos][position] = SmallestNum;
            mNewMatrix[position][LeftPos] = SmallestNum;
            visited[position] = 1;
        }
    }
    Print(mNewMatrix);
    for (int i = 0; i < mVexNum;i++)
    {
        delete[] mNewMatrix[i];
    }
    delete[] mNewMatrix;
}
struct SingleRoute
{
    /* data */
public:
    int PosA;
    int PosB;
    int weight;
    friend bool operator < (SingleRoute a,SingleRoute b)
    {
        return a.weight > b.weight;
    }
    SingleRoute(int PosA,int PosB,int weight)
    {
        this->PosA = PosA;
        this->PosB = PosB;
        this->weight = weight;
    }
    
    SingleRoute()
    {
        this->PosA = 0;
        this->PosB = 0;
        this->weight = INFINITY;
    }
};


void MapMatrix::Kruskal()
{
    cout << "Kruskal:" << endl;
    int **mNewMatrix;
    mNewMatrix = new int*[mVexNum];
    //先生成新的矩阵
    for (int i = 0; i < mVexNum; i++)
    {
        mNewMatrix[i] = new int[mVexNum];
    }
    Init(mNewMatrix);
    priority_queue<SingleRoute> queueForSearch;
    for (int i = 0; i < mVexNum; i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            if(i>=j)
            {
                SingleRoute route(i,j,mMatrix[i][j]);
                queueForSearch.push(route);
            }
        }
    }//构成优先队列
    //判断是否在一个连通分量中
    vector<SingleRoute> MST;
    UpSet set(mVexNum);
    
    while(MST.size()<mVexNum-1)
    {
        if(!queueForSearch.empty())
        {
            SingleRoute smallest;
            smallest = queueForSearch.top();
            queueForSearch.pop();
            int v = smallest.PosA;
            int u = smallest.PosB;
            if(set.Find(v)!=set.Find(u))
            {
                set.Union(v, u);
                MST.push_back(smallest);
                mNewMatrix[v][u] = smallest.weight;
                mNewMatrix[u][v] = smallest.weight;
            }
        }
        else
        {
            return;
        }
    }
    Print(mNewMatrix);
    for (int i = 0; i < mVexNum;i++)
    {
        delete[] mNewMatrix[i];
    }
    delete[] mNewMatrix;
}

Dist * MapMatrix::Dijikstra(int s)
{
    Dist *D = new Dist[mVexNum];
    int visited[mVexNum];
    
    for (int i = 0; i < mVexNum; i++)
    {
        visited[i] = 0;
        D[i].length = INFINITY;
        D[i].pre = s;
    }
    
    D[s].length = 0;
    int smallest = 0;
    for (int i = 0; i < mVexNum; i++)
    {
        while(visited[smallest])
        {
            smallest = (++smallest) % 6;
        }
        for (int j = 0; j < mVexNum;j++)
        {
            if(D[smallest].length>D[j].length&&!visited[j])
            {
                smallest = j;
            } 
            
        }
        cout << "smallest:" << smallest << endl;
        if (D[smallest].length == INFINITY)
        {
            break;
        }
        visited[smallest] = 1;
        //刷新D中的值，因为v的加入D的值需要改变
        //只要刷新与v相邻的点
        //第一次找的是自己
        for (int i = 0; i < mVexNum;i++)
        {
            if(D[i].length>(D[smallest].length+mMatrix[smallest][i]))
            {
                D[i].length = D[smallest].length + mMatrix[smallest][i];
                D[i].pre = smallest;
            }
        }
        
    }
   
    cout << "现在开始表示迪杰斯特拉路径结果" << endl;
    for (int i = 0; i < mVexNum;i++)
    {
        cout << i << " ";
    }
    cout << endl;
    for (int i = 0; i < mVexNum;i++)
    {
        cout << D[i].length << " ";
    }
    cout << endl;
    for (int i = 0; i < mVexNum;i++)
    {
        cout << D[i].pre << " ";
    }
    cout << endl;
    return D;
}

Dist **MapMatrix::Flyod()
{
    Dist ** D = new Dist *[mVexNum];
    for (int i = 0; i < mVexNum;i++)
    {
        D[i] = new Dist[mVexNum];
    }
    for (int i = 0; i < mVexNum;i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            if(i==j)
            {
                D[i][j].length = 0;
                D[i][j].pre = 0;
            }
            else
            {
                D[i][j].length = INFINITY;
                D[i][j].pre = -1;
            }
        }
        for (int i = 0; i < mVexNum;i++)
        {
            for (int j = 0; j < mVexNum;j++)
            {
                D[i][j].length = mMatrix[i][j];
                D[i][j].pre = i;
            }
        }
        for (int v = 0; v < mVexNum;v++)
        {
           
            for (int i = 0; i < mVexNum; i++)
            {
                for (int j = 0; j < mVexNum;j++)
                {
                    
                    if(D[i][j].length>D[i][v].length+D[v][j].length)
                    {
                        
                        D[i][j].length = D[i][v].length + D[v][j].length;
                        D[i][j].pre = D[v][j].pre;
                    }
                }
            }
        }
    }
    cout<<"弗洛伊德算法的展示"<<endl;
    cout << "Length:" << endl;
    for (int i = 0; i < mVexNum; i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            cout << D[i][j].length<<" ";
        }
        cout << endl;
    }
    cout << "Pre:" << endl;
    for (int i = 0; i < mVexNum; i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            cout << D[i][j].pre<<" ";
        }
        cout << endl;
    }
    

    return D;
    
}

int main()
{
    cout << "graph1部分..............." << endl;
    MapMatrix *graph = new MapMatrix(6);
    graph->Insert("Graph.txt");
    graph->BFSsearch();
    graph->Prim();
    graph->Kruskal();
    cout << "graph2部分................." << endl;
    MapMatrix *graph2 = new MapMatrix(6);
    graph2->Insert("Graph2.txt");
    Dist * D = graph2->Dijikstra(0);
    delete[] D;
    MapMatrix *graph3 = new MapMatrix(4);
    graph3->Insert("Graph3.txt");
    Dist ** DP = graph3->Flyod();
    
    delete graph;
    delete graph2;
    delete graph3;
    
    for (int i = 0; i < 4; i++)
    {
        delete[] DP[i];
    }
    
    delete[] DP;
}